package com.lizk.union_find;

/**
 * 并查集，解决连接问题
 * 网络中的两个节点是否相连？
 * 这里实现最基本的并查集，实现思路：
 * 1.用数组来存储每个节点
 * 2.每个节点都有一个level，相连接的节点的level相等。
 * 3.判断两个节点是否相等的时候只需要判断level是否相等即可
 * 4.将两个节点相连的时候只需要把所有等于第一个节点的level的节点的level值修改为第二个节点的level值
 * @author lizhikui
 * @date 2020/2/14 16:19
 */
public class UnionFindBase {
    public static class Node{
        int id;
        int level;
    }

    Node[] nodes ;

    public UnionFindBase(int length){
        nodes = new Node[length];
        for (int i = 0; i < length; i++) {
            Node node = new Node();
            node.id = i ;
            node.level = i;

            nodes[i] = node;
        }
    }

    private int find (int id){
        return nodes[id].level;
    }

    public void union (int one,int two){
        if (isConn(one,two)){
            return;
        }
        for (Node node : nodes) {
            if (node.level == nodes[one].level){
                node.level = nodes[two].level;
            }
        }
    }

    public boolean isConn(int one,int two){
        return nodes[one].level == nodes[two].level;
    }

}
